class Solution {
private:
    vector<vector<string>> res;
    vector<string> path;
    vector<vector<bool>> dp;
    int n;

    void dfs(string& s, int pos)
    {
        if(pos == n) // 递归终止条件：已经处理完整个字符串
        {
            res.push_back(path);
            return;
        }
 
        for(int i = pos; i < n; ++i) // 剪枝，尝试所有可能的分割点
        {
            if (dp[pos][i]) 
            {
                path.push_back(s.substr(pos,  i - pos + 1));
                dfs(s, i + 1);
                path.pop_back(); // 恢复现场
            }
        }
    }

    void dfs2(string& s, int start)
    {
        if (start == s.size()) // 递归终止条件：已经处理完整个字符串
        {
            res.push_back(path);
            return;
        }
        for (int end = start; end < s.size(); end++) // 尝试所有可能的分割点
        {
            if (dp[start][end]) 
            {
                path.push_back(s.substr(start, end - start + 1));
                dfs(s, end + 1);
                path.pop_back();
            }
        }
    }
public:
    vector<vector<string>> partition(string s) {
        n = s.size();
        dp.resize(n, vector<bool>(n, false));
        for(int i = n - 1; i >= 0; --i)
        {
            for(int j = i; j < n; ++j)
            {
                if(s[i] == s[j])
                    dp[i][j] = i + 1 >= j ? true : dp[i + 1][j - 1];
            }
        }
        dfs(s, 0);
        return res;
    }
};